package my.datastructures;

import java.util.Collection;
import java.util.SortedMap;
import java.util.TreeMap;

public class ConsistentHash<T>
{	
	private final HashFunction hashFunction;
	private final int numberOfReplicas;
	private final SortedMap<Integer, T> circle = new TreeMap<Integer, T>();

	public ConsistentHash(HashFunction hashFunction, int numberOfReplicas,
			Collection<T> nodes)
	{

		this.hashFunction = hashFunction;
		this.numberOfReplicas = numberOfReplicas;

		for (T node : nodes)
		{
			add(node);
		}
	}

	public void add(T node)
	{
		// Add the node and N replicas to the ring
		for (int i = 0; i < numberOfReplicas; i++)
		{
			circle.put(hashFunction.hash(node.toString() + i), node);
		}
	}

	public void remove(T node)
	{
		// Remove the node and N replicas from the ring
		for (int i = 0; i < numberOfReplicas; i++)
		{
			circle.remove(hashFunction.hash(node.toString() + i));
		}
	}

	public T get(Object key)
	{
		// there are no nodes
		if (circle.isEmpty())
		{
			return null;
		}
		
		// where does this data go?
		int hash = hashFunction.hash(key);
		
		// if the circle doesn't have the exact key and it probably won't
		if (!circle.containsKey(hash))
		{
			//grab all the keys bigger than my hash
			SortedMap<Integer, T> tailMap = circle.tailMap(hash);
			// if there are none we've wrapped around the ring, otherwise just grab the next one from me
			hash = tailMap.isEmpty() ? circle.firstKey() : tailMap.firstKey();
		}
		// returnt the found node
		return circle.get(hash);
	}
	
	class HashFunction
	{
		public int hash(Object key)
		{
			//TODO some fun MD5 action or something
			return 0;
		}
	}

}
